package com.xiaojianhx.demo.algorithm.sort;

import java.util.Arrays;

/**
 * 08 基数排序
 * 
 * @author xiaojianhx
 * @version V1.0.0 $ 2021-08-30 23:31:02 init ---- xiaojianhx
 */
public class Algorithm_Sort_08_RadixSort {

    private static int[] P = { 1, 10, 100, 1000, 10000, 100_000, 1_000_000, 10_000_000, 100_000_000, 1_000_000_000 };

    public static void lsd(int[] arr) {

        var base = 10;
        var len = arr.length;

        var buckets = new int[base][len];
        var cnt_tmp = new int[base];

        for (var tmp : buckets) {
            Arrays.fill(tmp, Integer.MIN_VALUE);
        }

        Arrays.fill(cnt_tmp, 0);

        var radix = 0;

        for (var i = 0; i < len; i++) {
            radix = Math.max(radix, String.valueOf(arr[i]).length());
        }

        for (var i = 1; i <= radix; i++) {

            for (var j = 0; j < len; j++) {
                var n = arr[j];
                var idx = n % P[i] / P[i - 1];
                buckets[idx][cnt_tmp[idx]++] = n;
            }

            var idx = 0;

            // 收回，并重置桶
            for (var j = 0; j < buckets.length; j++) {
                for (var k = 0; k < buckets[j].length; k++) {
                    if (buckets[j][k] > Integer.MIN_VALUE) {
                        arr[idx++] = buckets[j][k];
                        buckets[j][k] = Integer.MIN_VALUE;
                    }
                }
            }

            Arrays.fill(cnt_tmp, 0);
        }
    }
}